
"""
bit operation

a^a = 0
a^0 = a
a^b^c = a^c^b
"""


# 1.
# swap 2 numbers without extra var

def exchange(num1, num2):
    num1 ^= num2
    num2 ^= num1
    num1 ^= num2
    return num1, num2


def test_exchange():

    import random
    num1 = [random.randint(0, 10000) for _ in range(100)]
    num2 = [random.randint(10001, 20000) for _ in range(100)]

    for x, y in zip(num1, num2):
        rx, ry = exchange(x, y)
        assert x == ry
        assert y == rx


# 2.
# an array of numbers, of which, there is one number occurs 1 time, and the others all occur 2 times.
# How to find this number?


def find_number(seq):
    return reduce(lambda x, y: x ^ y, seq, 0)


def test_find_number():
    import random
    for _ in xrange(100):
        random_seq = [random.randint(0, 10000) for _ in xrange(100)] * 2
        alone = random.randint(0, 10000)
        random_seq.append(alone)
        assert alone == find_number(random_seq)


# 2.1
# an array of numbers, of which, there are 2 numbers of them occur 1 time, and all the others occur 2 times.
# how to find these 2 number?


def find_2_number(seq):
    temp = reduce(lambda x, y: x ^ y, seq, 0)
    index = find_first_1_bit(temp)
    rx = ry = 0
    for item in seq:
        if is_bit_zero(item, index):
            rx ^= item
        else:
            ry ^= item
    return rx, ry


def find_first_1_bit(num):
    i = 0
    while num & 1 == 0 and i < 32:
        num >>= 1
        i += 1
    return i


def is_bit_zero(num, index):
    assert index < 32
    num >>= index
    return num & 1 == 0


def test_find_2_number():
    import random
    for _ in xrange(100):
        random_seq = [random.randint(0, 10000) for _ in xrange(100)] * 2
        alonex = random.randint(0, 10000)
        aloney = random.randint(10001, 20000)
        random_seq.insert(random.randint(0, len(random_seq)-1), alonex)
        random_seq.insert(random.randint(0, len(random_seq)-1), aloney)
        rx, ry = find_2_number(random_seq)
        assert (alonex, aloney) == (rx, ry) or (alonex, aloney) == (ry, rx)

if __name__ == '__main__':
    test_exchange()
    test_find_number()
    test_find_2_number()
